/************************************************************************************************
 * @name    SequenceStack.c
 * @brief   这是顺序栈的代码案例，主要学习顺序栈的数据元素的增删改查，并设计API接口
 * @date    2024/12/24
 * @anchor  boluzs@163.com
 * @note
 *          1.栈的思想是“先进先出”，并且栈的特点是只能在栈的一端进行增删，这一段被称为“栈顶”
 *          2.把数据元素加入到栈的动作被称为“入栈\压栈”，英文是PUSH
 *          3.把数据元素从栈删除的动作被称为“出栈\弹栈”，英文是POP
 *          4.如果使用顺序表实现栈的思想，则只需要实现数据入栈（尾插法）+数据出栈（尾删法）
 * @version 1.0.0
 *
 * 版权声明
 * CopyRight (c)   2024-2025   boluzs@163.com    All Right Reciver
 *
 *************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>
typedef int DataType_t; // 用于说明顺序栈数据元素的类型 提高程序的可移植性

typedef struct SequenceStack
{
    unsigned int Size;      // 用于记录顺序栈的容量
    int Top;                // 用于记录顺序栈的起始地址
    DataType_t *BottomAddr; // 记录
} SqStack_t, *SqStack_p;

/************************************************************************************************
 *       @name   SqStack_Create
 *       @brief  创建顺序栈
 *       @param  Size: 指顺序栈的容量
 *       @note   None
 *       @retval 函数调用成功，返回指向SqlList_t类型的指针
 *************************************************************************************************/
SqStack_p SqStack_Create(unsigned int Size)
{
    // 1.为管理顺序栈的结构体申请堆内存并做错误处理
    // calloc函数返回一个void*类型的指针;
    SqStack_p Pmanager = (SqStack_p)calloc(1, sizeof(SqStack_t));
    if (NULL == Pmanager)
    {
        // perror("Calloc For SqStack_t Error");
        fprintf(stderr, "Calloc For SqStack_t Error,errno = %d,%s\n", errno, strerror(errno));
        exit(-1); // 导致程序终止
    }

    // 2.为顺序栈的数据元素申请堆内存，并进行错误处理
    DataType_t *Padder = (DataType_t *)calloc(Size, sizeof(DataType_t));
    if (NULL == Padder)
    {
        // perror("Calloc For SqStack_t Error");
        fprintf(stderr, "Calloc For Data Element Error,errno = %d,%s\n", errno, strerror(errno));
        exit(-1); // 导致程序终止
    }

    // 3.需要对顺序栈的管理结构体成员进行赋值
    Pmanager->Size = Size;         // 记录容量
    Pmanager->Top = -1;            // 记录下标
    Pmanager->BottomAddr = Padder; // 记录地址

    // 4.返回地址，并输出调试信息
    printf("SequenceStack Create Successfully!\n");
    return Pmanager;
};

/************************************************************************************************
 *       @name   SqStack_IsFull
 *       @brief  判断顺序栈是否已满
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @note   None
 *       @retval 顺序栈已满，返回true，顺序栈已满，返回false
 *************************************************************************************************/
bool SqStack_IsFull(SqStack_p Pmanager)
{
    return (Pmanager->Top == Pmanager->Size - 1) ? true : false;
}

/************************************************************************************************
 *       @name   SqStack_IsEmpty
 *       @brief  判断顺序栈是否已满
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @note   None
 *       @retval 顺序栈为空，返回true，顺序栈不为空，返回false
 *************************************************************************************************/
bool SqStack_IsEmpty(SqStack_p Pmanager)
{
    return (Pmanager->Top == -1) ? true : false;
}

/************************************************************************************************
 *       @name   SqStack_TailInsert
 *       @brief  向顺序栈的尾部插入新元素
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @param  Data: 指待插入顺序栈的数据元素的值
 *       @note   插入元素之前需要先检查顺序栈是否已满
 *       @retval 插入成功，返回true，插入失败，返回false
 *************************************************************************************************/
bool SqStack_Push(SqStack_p Pmanager, DataType_t Data)
{
    // 为了提高程序的可靠性，所以需要对指针进行备份
    SqStack_p P = Pmanager;

    // 1、检查参数有效性
    if (NULL == Pmanager)
    {
        fprintf(stderr, "Insert Error, Argument Is Invalid\n");
        return false;
    }

    // 2、检查顺序栈容量
    if (SqStack_IsFull(P))
    {
        fprintf(stderr, "Insert Error, SqStack Is Full\n");
        return false;
    }

    // 3、更新顺序栈的属性
    Pmanager->Top++;
    // 4、顺序栈插入元素
    Pmanager->BottomAddr[Pmanager->Top] = Data;

    return true;
}

/************************************************************************************************
 *       @name   SqStack_Pop
 *       @brief  删除顺序栈的尾部元素
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @note   删除元素之前需要先检查顺序栈是否为空
 *       @retval 出栈返回元素值
 *************************************************************************************************/
DataType_t SqStack_Pop(SqStack_p Pmanager)
{
    // 为了提高程序的可靠性，所以需要对指针进行备份
    SqStack_p P = Pmanager;

    // 1、检查参数有效性
    if (NULL == Pmanager)
    {
        fprintf(stderr, "Delete Error, Argument Is Invalid\n");
        exit(-1);
    }

    // 2、检查顺序栈容量
    if (SqStack_IsEmpty(P))
    {
        fprintf(stderr, "Delete Error, SqStack Is Empty\n");
        exit(-1);
    }

    // 3、备份需要弹出的元素
    DataType_t temp = Pmanager->BottomAddr[Pmanager->Top];
    // 4、更新顺序栈的下标
    Pmanager->Top--;

    return temp;
}

/************************************************************************************************
 *       @name   SqStack_Print
 *       @brief  遍历顺序栈
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @note   None
 *       @retval 遍历成功，返回true，遍历失败，返回false
 *************************************************************************************************/
bool SqStack_Print(SqStack_p Pmanager)
{
    // 为了提高程序的可靠性，所以需要对指针进行备份
    SqStack_p P = Pmanager;

    // 1、检查参数有效性
    if (NULL == Pmanager)
    {
        fprintf(stderr, "Print Error, Argument Is Invalid\n");
        return false;
    }

    // 2、对顺序栈的元素进行遍历
    for (int i = 0; i <= P->Top; i++)
    {
        printf("SqStack Element[%d] = %d\n", i, P->BottomAddr[i]);
    }
    return true;
}

/**************************************************************************
 * @name: SqStack_Dec2Hex
 * @brief: 实现十进制转十六进制
 * @param {SqStack_p} Pmanager：指向顺序栈的地址
 * @note: None
 * @retval: None
 **************************************************************************/
void SqStack_Dec2Hex(SqStack_p Pmanager)
{
    // 为了提高程序的可靠性，所以需要对指针进行备份
    SqStack_p P = Pmanager;

    // 1、检查参数有效性
    if (NULL == P)
    {
        fprintf(stderr, "Dec2Hex Error, Argument Is Invalid\n");
        exit(-1);
    }

    // 2、输入一个正整数
    int n = 0;
    int Data = 0;
    while (n != 1)
    {
        printf("请输入一个正整数\n");
        n = scanf("%d", &Data);
        if (n != 1)
            printf("输入的数据类型有误, 请重新输入\n");
        while (getchar() != '\n')
            ;
    }

    // 2、循环判断
    while (Data != 0)
    {
        // 3、将余数入栈
        SqStack_Push(P, Data % 16);

        // 4、保存除数
        Data /= 16;
    }

    // 5、遍历弹出栈中元素
    printf("0x");
    while (P->Top != -1)
    {
        // 7、判断弹出的元素是否需要转换字符
        int Stack_Data = SqStack_Pop(P);
        if (Stack_Data >= 10)
        {
            printf("%c", Stack_Data + 55);
        }
        else
        {
            printf("%d", Stack_Data);
        }
    }
    printf("\n");
}

/**************************************************************************
 * @name:   None
 * @brief:  通过键盘输入一个包括 '('和')'的字符串 string，判断字符串是否有效。
 *          要求设计算法实现检查字符串是否有效，有效的字符串需满足以下条件:
 * @note:
            1.左括号必须用相同类型的右括号闭合。
            2.左括号必须以正确的顺序闭合。
            3.每个右括号都有一个对应的相同类型的左括号
 * @retval: 遍历成功，返回true，遍历失败，返回false
 **************************************************************************/
bool SqStack_CheckStr(SqStack_p Pmanager)
{
    // 为了提高程序的可靠性，所以需要对指针进行备份
    SqStack_p P = Pmanager;

    // 1、检查参数有效性
    if (NULL == P)
    {
        fprintf(stderr, "CheckStr Error, Argument Is Invalid\n");
        exit(-1);
    }

    // 2、输入一个表达式
    int n = 0;
    char *str = (char *)calloc(1, 128);
    while (n != 1)
    {
        printf("请输入一个表达式\n");
        n = scanf("%s", str);
        if (n != 1)
            printf("输入的数据类型有误, 请重新输入\n");
        while (getchar() != '\n')
            ;
    }

    // 3、遍历字符串
    for (int i = 0; str[i] != '\0'; i++)
    {
        // 4、将'('PUSH到栈
        if ('(' == str[i])
        {
            SqStack_Push(P, '(');
        }
        // 5、判断栈不为空并且当前元素为')'
        else if (')' == str[i] && !SqStack_IsEmpty(P))
        {
            SqStack_Pop(P);
        }
        else if (')' == str[i] && SqStack_IsEmpty(P))
        {
            printf("表达式不合法\n");
            return false;
        }
    }
    free(str);
    if (SqStack_IsEmpty(P))
    {
        printf("表达式合法\n");
        return true;
    }
    else
    {
        printf("表达式不合法\n");
        return false;
    }
}

/************************************************************************************************
 *       @name   SqStack_Distory
 *       @brief  释放顺序栈内存以及元素内存
 *       @param  Pmanager: 指记录顺序栈属性的结构体指针
 *       @param  Paddr: 指记录顺序栈里面元素的指针
 *       @note   None
 *       @retval 函数调用成功，返回true，调用失败，返回false
 *************************************************************************************************/
bool SqStack_Destory(SqStack_p Pmanager, DataType_t *Paddr)
{
    // 备份指针
    SqStack_p P = Pmanager;

    // 1.释放顺序栈的堆内存
    free(Pmanager);
    free(Paddr);
    // 2.释放顺序栈的数据元素的堆内存
    return true;
};

/**************************************************************************
 * @name: isQueueEmpty
 * @brief: 利用两个栈模拟队列是否为空
 * @param {SqStack_p} s1:记录队列进栈
 * @param {SqStack_p} s2:记录队列出栈
 * @note: None
 * @retval: 成功，返回true，失败，返回false
 **************************************************************************/
bool isQueueEmpty(SqStack_p s1, SqStack_p s2)
{
    return SqStack_IsEmpty(s1) && SqStack_IsEmpty(s2) ? true : false;
}

/**************************************************************************
 * @name: enQueue
 * @brief: 利用两个栈模拟队列入队操作
 * @param {SqStack_p} s1:记录队列进栈
 * @param {SqStack_p} s2:记录队列出栈
 * @param {int} x
 * @note: None
 * @retval: 成功，返回true，失败，返回false
 **************************************************************************/
bool enQueue(SqStack_p s1, SqStack_p s2, int x)
{
    // 判断s1是否满了并且s2中是否还有元素尚未弹出
    if (SqStack_IsFull(s1) && !SqStack_IsEmpty(s2))
    {
        fprintf(stderr, "enQueue Error, StackQueue Is Full\n");
        return false;
    }
    // 判断s1是否满了并且s2中是否还有元素尚未弹出
    else if (SqStack_IsFull(s1) && SqStack_IsEmpty(s2))
    {
        while (!SqStack_IsEmpty(s1))
        {
            SqStack_Push(s2, SqStack_Pop(s1));
        }
    }
    SqStack_Push(s1, x);
    printf("入队成功\n");
    return true;
}

/**************************************************************************
 * @name: deQueue
 * @brief: 利用两个栈模拟队列出队操作
 * @param {SqStack_p} s1:记录队列进栈
 * @param {SqStack_p} s2:记录队列出栈
 * @note: None
 * @retval: 返回弹出的元素
 **************************************************************************/
int deQueue(SqStack_p s1, SqStack_p s2)
{
    if (isQueueEmpty(s1, s2))
    {
        fprintf(stderr, "deQueue Error, StackQueue Is Empty\n");
        exit(-1);
    }
    // 判断s2是否为空，空的话则将s1的元素移到s2中再进行出队
    if (SqStack_IsEmpty(s2))
    {
        while (!SqStack_IsEmpty(s1))
        {
            SqStack_Push(s2, SqStack_Pop(s1));
        }
    }
    return SqStack_Pop(s2);
}

/**
 * @name:   main
 * @brief:  主函数
 * @param   None
 * @note:   None
 * @retval: 调用成功，返回0，调用失败，返回-1
 */
int main(int argc, char const *argv[])
{
    // 1、创建顺序栈
    SqStack_p sq_stack_p = SqStack_Create(128);
    SqStack_p s1 = SqStack_Create(3);
    SqStack_p s2 = SqStack_Create(3);

    // 2、向尾部插入元素
    // SqStack_Push(sq_stack_p, 1);
    // SqStack_Push(sq_stack_p, 3);
    // SqStack_Push(sq_stack_p, 5);
    // SqStack_Push(sq_stack_p, 7);
    // SqStack_Push(sq_stack_p, 9);

    // 4、遍历顺序栈
    // printf("弹出的元素：%d\n", SqStack_Pop(sq_stack_p));
    // printf("弹出的元素：%d\n", SqStack_Pop(sq_stack_p));
    // printf("弹出的元素：%d\n", SqStack_Pop(sq_stack_p));
    // printf("弹出的元素：%d\n", SqStack_Pop(sq_stack_p));
    // printf("弹出的元素：%d\n", SqStack_Pop(sq_stack_p));

    // 5、遍历顺序栈
    // SqStack_Print(sq_stack_p);

    // 6、十进制转十六进制
    // SqStack_Dec2Hex(sq_stack_p);

    // 7、校验表达式是否合法
    // SqStack_CheckStr(sq_stack_p);

    // 8、模拟队列操作
    enQueue(s1, s2, 1);
    enQueue(s1, s2, 2);
    enQueue(s1, s2, 3);
    enQueue(s1, s2, 4);
    enQueue(s1, s2, 5);
    enQueue(s1, s2, 6);
    printf("弹出的元素：%d\n", deQueue(s1, s2));
    printf("弹出的元素：%d\n", deQueue(s1, s2));

    enQueue(s1, s2, 7);
    enQueue(s1, s2, 8);
    printf("弹出的元素：%d\n", deQueue(s1, s2));
    printf("弹出的元素：%d\n", deQueue(s1, s2));
    printf("弹出的元素：%d\n", deQueue(s1, s2));
    
    // 释放内存
    SqStack_Destory(sq_stack_p, sq_stack_p->BottomAddr);
    SqStack_Destory(s1, s1->BottomAddr);
    SqStack_Destory(s2, s2->BottomAddr);
    return 0;
}
